class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        vector<int> sum(n+1,-1);
        sum[0]=0;
        sum[1]=nums[0];
        for(int i=2;i<=n;i++){
            sum[i]=max(sum[i-2]+nums[i-1],sum[i-1]);
        }
        return sum[n];
    }
};
